using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace CSharpBasicsExamples.DataStructures
{
    // 数据结构示例：数组与链表
    
    // 自定义链表节点
    public class ListNode<T>
    {
        public T Data { get; set; }
        public ListNode<T> Next { get; set; }
        
        public ListNode(T data)
        {
            Data = data;
            Next = null;
        }
        
        public override string ToString()
        {
            return Data?.ToString() ?? "null";
        }
    }
    
    // 自定义单向链表实现
    public class CustomLinkedList<T>
    {
        private ListNode<T> head;
        private int count;
        
        public int Count => count;
        public bool IsEmpty => head == null;
        
        // 在头部添加节点 O(1)
        public void AddFirst(T data)
        {
            var newNode = new ListNode<T>(data);
            newNode.Next = head;
            head = newNode;
            count++;
        }
        
        // 在尾部添加节点 O(n)
        public void AddLast(T data)
        {
            var newNode = new ListNode<T>(data);
            
            if (head == null)
            {
                head = newNode;
            }
            else
            {
                var current = head;
                while (current.Next != null)
                {
                    current = current.Next;
                }
                current.Next = newNode;
            }
            count++;
        }
        
        // 在指定位置插入 O(n)
        public void Insert(int index, T data)
        {
            if (index < 0 || index > count)
                throw new ArgumentOutOfRangeException(nameof(index));
            
            if (index == 0)
            {
                AddFirst(data);
                return;
            }
            
            var newNode = new ListNode<T>(data);
            var current = head;
            
            for (int i = 0; i < index - 1; i++)
            {
                current = current.Next;
            }
            
            newNode.Next = current.Next;
            current.Next = newNode;
            count++;
        }
        
        // 删除指定值的第一个节点 O(n)
        public bool Remove(T data)
        {
            if (head == null) return false;
            
            // 如果要删除的是头节点
            if (head.Data.Equals(data))
            {
                head = head.Next;
                count--;
                return true;
            }
            
            var current = head;
            while (current.Next != null)
            {
                if (current.Next.Data.Equals(data))
                {
                    current.Next = current.Next.Next;
                    count--;
                    return true;
                }
                current = current.Next;
            }
            
            return false;
        }
        
        // 删除指定位置的节点 O(n)
        public void RemoveAt(int index)
        {
            if (index < 0 || index >= count)
                throw new ArgumentOutOfRangeException(nameof(index));
            
            if (index == 0)
            {
                head = head.Next;
                count--;
                return;
            }
            
            var current = head;
            for (int i = 0; i < index - 1; i++)
            {
                current = current.Next;
            }
            
            current.Next = current.Next.Next;
            count--;
        }
        
        // 查找节点 O(n)
        public bool Contains(T data)
        {
            var current = head;
            while (current != null)
            {
                if (current.Data.Equals(data))
                    return true;
                current = current.Next;
            }
            return false;
        }
        
        // 获取指定位置的元素 O(n)
        public T Get(int index)
        {
            if (index < 0 || index >= count)
                throw new ArgumentOutOfRangeException(nameof(index));
            
            var current = head;
            for (int i = 0; i < index; i++)
            {
                current = current.Next;
            }
            
            return current.Data;
        }
        
        // 设置指定位置的元素 O(n)
        public void Set(int index, T data)
        {
            if (index < 0 || index >= count)
                throw new ArgumentOutOfRangeException(nameof(index));
            
            var current = head;
            for (int i = 0; i < index; i++)
            {
                current = current.Next;
            }
            
            current.Data = data;
        }
        
        // 清空链表
        public void Clear()
        {
            head = null;
            count = 0;
        }
        
        // 转换为数组
        public T[] ToArray()
        {
            T[] array = new T[count];
            var current = head;
            int index = 0;
            
            while (current != null)
            {
                array[index++] = current.Data;
                current = current.Next;
            }
            
            return array;
        }
        
        // 遍历显示
        public void Display()
        {
            if (head == null)
            {
                Console.WriteLine("链表为空");
                return;
            }
            
            var current = head;
            while (current != null)
            {
                Console.Write($"{current.Data}");
                if (current.Next != null)
                    Console.Write(" -> ");
                current = current.Next;
            }
            Console.WriteLine(" -> null");
        }
        
        // 反转链表
        public void Reverse()
        {
            ListNode<T> prev = null;
            ListNode<T> current = head;
            ListNode<T> next = null;
            
            while (current != null)
            {
                next = current.Next;
                current.Next = prev;
                prev = current;
                current = next;
            }
            
            head = prev;
        }
    }
    
    // 自定义动态数组实现
    public class CustomDynamicArray<T>
    {
        private T[] items;
        private int size;
        private const int DefaultCapacity = 4;
        
        public int Count => size;
        public int Capacity => items.Length;
        public bool IsEmpty => size == 0;
        
        public CustomDynamicArray()
        {
            items = new T[DefaultCapacity];
            size = 0;
        }
        
        public CustomDynamicArray(int capacity)
        {
            if (capacity < 0)
                throw new ArgumentOutOfRangeException(nameof(capacity));
            
            items = new T[capacity];
            size = 0;
        }
        
        // 索引器 O(1)
        public T this[int index]
        {
            get
            {
                if (index < 0 || index >= size)
                    throw new ArgumentOutOfRangeException(nameof(index));
                return items[index];
            }
            set
            {
                if (index < 0 || index >= size)
                    throw new ArgumentOutOfRangeException(nameof(index));
                items[index] = value;
            }
        }
        
        // 添加元素 平均O(1)，最坏O(n)
        public void Add(T item)
        {
            if (size == items.Length)
            {
                EnsureCapacity(size + 1);
            }
            items[size++] = item;
        }
        
        // 在指定位置插入 O(n)
        public void Insert(int index, T item)
        {
            if (index < 0 || index > size)
                throw new ArgumentOutOfRangeException(nameof(index));
            
            if (size == items.Length)
            {
                EnsureCapacity(size + 1);
            }
            
            // 向后移动元素
            for (int i = size; i > index; i--)
            {
                items[i] = items[i - 1];
            }
            
            items[index] = item;
            size++;
        }
        
        // 删除指定位置的元素 O(n)
        public void RemoveAt(int index)
        {
            if (index < 0 || index >= size)
                throw new ArgumentOutOfRangeException(nameof(index));
            
            // 向前移动元素
            for (int i = index; i < size - 1; i++)
            {
                items[i] = items[i + 1];
            }
            
            size--;
            items[size] = default(T); // 清理引用
        }
        
        // 删除指定值的第一个元素 O(n)
        public bool Remove(T item)
        {
            int index = IndexOf(item);
            if (index >= 0)
            {
                RemoveAt(index);
                return true;
            }
            return false;
        }
        
        // 查找元素索引 O(n)
        public int IndexOf(T item)
        {
            for (int i = 0; i < size; i++)
            {
                if (items[i].Equals(item))
                    return i;
            }
            return -1;
        }
        
        // 检查是否包含元素 O(n)
        public bool Contains(T item)
        {
            return IndexOf(item) >= 0;
        }
        
        // 清空数组
        public void Clear()
        {
            for (int i = 0; i < size; i++)
            {
                items[i] = default(T);
            }
            size = 0;
        }
        
        // 转换为数组
        public T[] ToArray()
        {
            T[] array = new T[size];
            Array.Copy(items, 0, array, 0, size);
            return array;
        }
        
        // 确保容量
        private void EnsureCapacity(int min)
        {
            if (items.Length < min)
            {
                int newCapacity = items.Length == 0 ? DefaultCapacity : items.Length * 2;
                if (newCapacity < min) newCapacity = min;
                
                T[] newItems = new T[newCapacity];
                Array.Copy(items, 0, newItems, 0, size);
                items = newItems;
            }
        }
        
        // 显示数组内容
        public void Display()
        {
            if (size == 0)
            {
                Console.WriteLine("数组为空");
                return;
            }
            
            Console.Write("[");
            for (int i = 0; i < size; i++)
            {
                Console.Write(items[i]);
                if (i < size - 1)
                    Console.Write(", ");
            }
            Console.WriteLine("]");
        }
    }
    
    // 性能测试类
    public class PerformanceTest
    {
        public static void ComparePerformance()
        {
            Console.WriteLine("=== 数据结构性能对比 ===\n");
            
            const int testSize = 10000;
            var stopwatch = new Stopwatch();
            
            // 测试数组的随机访问性能
            Console.WriteLine("1. 随机访问性能测试:");
            
            // 数组随机访问
            int[] array = new int[testSize];
            for (int i = 0; i < testSize; i++)
            {
                array[i] = i;
            }
            
            stopwatch.Start();
            for (int i = 0; i < testSize; i++)
            {
                int value = array[i]; // O(1) 访问
            }
            stopwatch.Stop();
            Console.WriteLine($"数组随机访问: {stopwatch.ElapsedMilliseconds} ms");
            
            // 链表顺序访问
            var linkedList = new CustomLinkedList<int>();
            for (int i = 0; i < testSize; i++)
            {
                linkedList.AddLast(i);
            }
            
            stopwatch.Restart();
            for (int i = 0; i < testSize; i++)
            {
                int value = linkedList.Get(i); // O(n) 访问
            }
            stopwatch.Stop();
            Console.WriteLine($"链表顺序访问: {stopwatch.ElapsedMilliseconds} ms");
            Console.WriteLine();
            
            // 测试插入性能
            Console.WriteLine("2. 插入性能测试:");
            
            // 数组头部插入
            var dynamicArray = new CustomDynamicArray<int>();
            stopwatch.Restart();
            for (int i = 0; i < 1000; i++)
            {
                dynamicArray.Insert(0, i); // O(n) 插入
            }
            stopwatch.Stop();
            Console.WriteLine($"动态数组头部插入: {stopwatch.ElapsedMilliseconds} ms");
            
            // 链表头部插入
            var testLinkedList = new CustomLinkedList<int>();
            stopwatch.Restart();
            for (int i = 0; i < 1000; i++)
            {
                testLinkedList.AddFirst(i); // O(1) 插入
            }
            stopwatch.Stop();
            Console.WriteLine($"链表头部插入: {stopwatch.ElapsedMilliseconds} ms");
            Console.WriteLine();
            
            // 测试内存使用
            Console.WriteLine("3. 内存使用对比:");
            TestMemoryUsage();
        }
        
        private static void TestMemoryUsage()
        {
            const int elementCount = 1000;
            
            // 数组内存使用
            long arrayMemory = GC.GetTotalMemory(true);
            int[] array = new int[elementCount];
            for (int i = 0; i < elementCount; i++)
            {
                array[i] = i;
            }
            arrayMemory = GC.GetTotalMemory(true) - arrayMemory;
            
            // 链表内存使用
            long linkedListMemory = GC.GetTotalMemory(true);
            var linkedList = new CustomLinkedList<int>();
            for (int i = 0; i < elementCount; i++)
            {
                linkedList.AddLast(i);
            }
            linkedListMemory = GC.GetTotalMemory(true) - linkedListMemory;
            
            Console.WriteLine($"数组内存使用: {arrayMemory} bytes");
            Console.WriteLine($"链表内存使用: {linkedListMemory} bytes");
            Console.WriteLine($"链表额外开销: {linkedListMemory - arrayMemory} bytes");
        }
    }
    
    // 主演示程序
    public class DataStructuresDemo
    {
        public static void RunDemo()
        {
            Console.WriteLine("=== 数据结构演示：数组与链表 ===\n");
            
            // 1. 链表操作演示
            DemonstrateLinkedList();
            
            // 2. 动态数组操作演示
            DemonstrateDynamicArray();
            
            // 3. 性能对比
            PerformanceTest.ComparePerformance();
            
            // 4. 使用场景建议
            ShowUsageRecommendations();
        }
        
        private static void DemonstrateLinkedList()
        {
            Console.WriteLine("=== 链表操作演示 ===");
            
            var linkedList = new CustomLinkedList<string>();
            
            // 添加元素
            linkedList.AddFirst("第一个");
            linkedList.AddLast("最后一个");
            linkedList.Insert(1, "中间的");
            
            Console.WriteLine("添加元素后:");
            linkedList.Display();
            Console.WriteLine($"元素数量: {linkedList.Count}");
            
            // 查找元素
            Console.WriteLine($"包含'中间的': {linkedList.Contains("中间的")}");
            Console.WriteLine($"索引1的元素: {linkedList.Get(1)}");
            
            // 删除元素
            linkedList.Remove("中间的");
            Console.WriteLine("删除'中间的'后:");
            linkedList.Display();
            
            // 反转链表
            linkedList.Reverse();
            Console.WriteLine("反转后:");
            linkedList.Display();
            Console.WriteLine();
        }
        
        private static void DemonstrateDynamicArray()
        {
            Console.WriteLine("=== 动态数组操作演示 ===");
            
            var dynamicArray = new CustomDynamicArray<int>();
            
            // 添加元素
            for (int i = 1; i <= 5; i++)
            {
                dynamicArray.Add(i * 10);
            }
            
            Console.WriteLine("添加元素后:");
            dynamicArray.Display();
            Console.WriteLine($"容量: {dynamicArray.Capacity}, 数量: {dynamicArray.Count}");
            
            // 插入元素
            dynamicArray.Insert(2, 999);
            Console.WriteLine("在索引2插入999后:");
            dynamicArray.Display();
            
            // 访问元素
            Console.WriteLine($"索引3的元素: {dynamicArray[3]}");
            
            // 修改元素
            dynamicArray[0] = 100;
            Console.WriteLine("修改索引0为100后:");
            dynamicArray.Display();
            
            // 删除元素
            dynamicArray.RemoveAt(2);
            Console.WriteLine("删除索引2的元素后:");
            dynamicArray.Display();
            Console.WriteLine();
        }
        
        private static void ShowUsageRecommendations()
        {
            Console.WriteLine("=== 使用场景建议 ===\n");
            
            Console.WriteLine("数组适用场景:");
            Console.WriteLine("✓ 需要频繁随机访问元素");
            Console.WriteLine("✓ 数据大小相对固定");
            Console.WriteLine("✓ 对内存使用效率要求高");
            Console.WriteLine("✓ 需要良好的缓存性能");
            Console.WriteLine("✓ 数值计算和科学计算");
            
            Console.WriteLine("\n链表适用场景:");
            Console.WriteLine("✓ 频繁插入和删除操作");
            Console.WriteLine("✓ 数据大小变化很大");
            Console.WriteLine("✓ 不需要随机访问");
            Console.WriteLine("✓ 实现其他数据结构（栈、队列）");
            Console.WriteLine("✓ 内存分配灵活性要求高");
            
            Console.WriteLine("\n性能特点总结:");
            Console.WriteLine("操作        | 数组  | 链表");
            Console.WriteLine("------------|-------|------");
            Console.WriteLine("随机访问    | O(1)  | O(n)");
            Console.WriteLine("头部插入    | O(n)  | O(1)");
            Console.WriteLine("尾部插入    | O(1)* | O(n)");
            Console.WriteLine("中间插入    | O(n)  | O(1)*");
            Console.WriteLine("删除        | O(n)  | O(1)*");
            Console.WriteLine("查找        | O(n)  | O(n)");
            Console.WriteLine("\n* 表示在已知位置的情况下");
        }
    }
}
